home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / pcr / pcr4_4.lha / DIST / gc / GCalloc.c < prev    next >
C/C++ Source or Header  |  1992-02-25  |  9KB  |  311 lines
  1. /* begincopyright
  2.   Copyright (c) 1988,1990 Xerox Corporation. All rights reserved.
  3.   Use and copying of this software and preparation of derivative works based
  4.   upon this software are permitted. Any distribution of this software or
  5.   derivative works must comply with all applicable United States export
  6.   control laws. This software is made available AS IS, and Xerox Corporation
  7.   makes no warranty about the software, its performance or its conformity to
  8.   any specification. Any person obtaining a copy of this software is requested
  9.   to send their name and post office or electronic mail address to:
  10.     PCR Coordinator
  11.     Xerox PARC
  12.     3333 Coyote Hill Rd.
  13.     Palo Alto, CA 94304
  14.     
  15.   Parts of this software were derived from code bearing the copyright notice:
  16.   
  17.   Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  18.   This material may be freely distributed, provided this notice is retained.
  19.   This material is provided as is, with no warranty expressed or implied.
  20.   Use at your own risk.
  21.   
  22.   endcopyright */
  23. /*
  24.  * This file contains the functions:
  25.  *      void GC_new_hblk(n, ll)
  26.  *    struct obj * GC_allocobj(sz)
  27.  *    struct obj * GC_allocaobj(sz)
  28.  */
  29.  
  30. /*
  31.  * Boehm, December 14, 1990 2:15:29 pm PST
  32.  */
  33.  
  34. # include <signal.h>
  35. # include <sys/types.h>
  36. # include <sys/times.h>
  37. # include <sys/timeb.h>
  38. # include "xr/GCPrivate.h"
  39.  
  40.  
  41. /* Leaving these defined enables output to stderr.  In order of */
  42. /* increasing verbosity:                                        */
  43. #define DEBUG            /* Verbose debugging output */
  44. #undef DEBUG
  45. #define DEBUG2           /* EXTREMELY verbose debugging output */
  46. #undef DEBUG2
  47.  
  48. /*
  49.  * This is an attempt at a garbage collecting storage allocator
  50.  * that should run on most UNIX systems.  The garbage
  51.  * collector is overly conservative in that it may fail to reclaim
  52.  * inaccessible storage.  On the other hand, it does not assume
  53.  * any runtime tag information.
  54.  * We make the following assumptions:
  55.  *  1.  We are running under something that looks like Berkeley UNIX,
  56.  *      on one of the supported architectures.
  57.  *  2.  For every accessible object, a pointer to it is stored 
  58.  *      somewhere where GC_mark_roots will find it.
  59.  */
  60.  
  61. /*
  62.  * Separate free lists are maintained for different sized objects
  63.  * up to MAXOBJSZ.
  64.  * The lists (GC_)objfreelist[i] contain free objects of size i which may
  65.  * contain nested pointers.  The lists aobjfreelist[i] contain free
  66.  * atomic objects, which may not contain nested pointers.
  67.  * The call allocobj(i) insures that objfreelist[i] points to a non-empty
  68.  * free list.
  69.  * GC_allocobj may be called to allocate an object of (small) size i
  70.  * as follows:
  71.  *
  72.  *            opp = &(GC_objfreelist[i]);
  73.  *            if (*opp == (struct obj *)0) GC_allocobj(i);
  74.  *            ptr = *opp;
  75.  *            *opp = ptr->next;
  76.  *
  77.  * Note that this is very fast if the free list is non-empty; it should
  78.  * only involve the execution of 4 or 5 simple instructions.
  79.  * All composite objects on freelists are cleared, except for
  80.  * their first longword.
  81.  */
  82.  
  83. /*
  84.  *  The allocator uses allochblk to allocate large chunks of objects.
  85.  * These chunks all start on addresses which are multiples of
  86.  * HBLKSZ.  All starting addresses are maintained on a contiguous
  87.  * list so that they can be traversed in the sweep phase of garbage collection.
  88.  * This makes it possible to check quickly whether an
  89.  * arbitrary address corresponds to an object administered by the
  90.  * allocator.
  91.  *  We make the (probably false) claim that this can be interrupted
  92.  * by a signal with at most the loss of some chunk of memory.
  93.  */
  94.  
  95. /* Declarations for fundamental data structures.  These are grouped */
  96. /* together, so that the collector can skip over them.              */
  97. /* This relies on some assumptions about the compiler that are not  */
  98. /* guaranteed valid, but ...                                        */
  99.  
  100. char GC_copyright[] = "Copyright 1990 Xerox Corporation, 1988,1989 Hans-J. Boehm and Alan J. Demers";
  101.  
  102. /*
  103.  * Allocate a new heapblock for objects of size n.
  104.  * Add all of the heapblock's objects to the free list for objects
  105.  * of that size.  A negative n requests atomic objects.
  106.  * Returns TRUE if successful, FALSE otherwise.
  107.  */
  108. bool GC_new_hblk(n)
  109. long n;
  110. {
  111.     register word *p,
  112.           *r;
  113.     word *last_object;        /* points to last object in new hblk    */
  114.     register struct hblk *h;    /* the new heap block            */
  115.     register long abs_sz;    /* |n|    */
  116.     register int i;
  117.  
  118.  
  119.   /* Allocate a new heap block */
  120.     h = GC_allochblk(n);
  121.     if (h == (struct hblk *)0) {
  122.         return(FALSE);
  123.     }
  124.  
  125.  
  126.   /* Add it to hblklist */
  127.     GC_add_hblklist(h);
  128.     
  129.   /* Keep track of the fact that we allocated it in this collection cycle */
  130.  
  131.     hb_last_reclaimed(h) = GC_gc_no;
  132.     
  133.   /* Add objects to free list */
  134.     abs_sz = abs(n);
  135.     p = &(h -> hb_body[abs_sz]);    /* second object in *h    */
  136.     r = &(h -> hb_body[0]);           /* One object behind p    */
  137.     last_object = ((word *)((char *)h + HBLKSIZE)) - abs_sz;
  138.                 /* Last place for last object to start */
  139.  
  140.   /* make a list of all objects in *h with head as last object */
  141.     while (p <= last_object) {
  142.       /* current object's link points to last object */
  143.     set_obj_link((struct obj *)p, r);
  144.     r = p;
  145.     p += abs_sz;
  146.     }
  147.     p -= abs_sz;            /* p now points to last object */
  148.  
  149.   /*
  150.    * put p (which is now head of list of objects in *h) as first
  151.    * pointer in the appropriate free list for this size.
  152.    */
  153.     if (n < 0) {
  154.       set_obj_link((struct obj *)(h -> hb_body), aobjfreelist[abs_sz]);
  155.       aobjfreelist[abs_sz] = ((struct obj *)p);
  156.     } else {
  157.       set_obj_link((struct obj *)(h -> hb_body), objfreelist[abs_sz]);
  158.       objfreelist[abs_sz] = ((struct obj *)p);
  159.     }
  160.     
  161.   /* Try to create a map of the block layout for fast access by the marker. */
  162.     GC_add_cache_entry(abs_sz);
  163.  
  164. #   ifdef DEBUG
  165.     GC_vprintf("Allocated new heap block at address 0x%X\n",
  166.           h);
  167. #   endif
  168.     return(TRUE);
  169. }
  170.  
  171.  
  172. # ifdef VISUALIZE
  173. /* Redisplay all marked objects in a block as allocated */
  174. undisplay_marks(hbp)
  175. register struct hblk *hbp;      /* ptr to current heap block            */
  176. {
  177.     register int word_no;       /* Number of word in block              */
  178.     register int sz;            /* size of objects in current block     */
  179.     register int i = 0;
  180.     int start_word_no;
  181.  
  182.     sz = HB_SIZE(hbp);
  183.     word_no = start_word_no = BYTES_TO_WORDS(HDR_BYTES);
  184.     while (word_no + sz <= BYTES_TO_WORDS(HBLKSIZE)
  185.        || word_no == start_word_no) {
  186.     if (mark_bit(hbp, word_no)) {
  187.         displayAlloc(((word *)hbp) + word_no, sz);
  188.     }
  189.     word_no += sz;
  190.     }
  191. }
  192. # endif
  193.  
  194.  
  195.  
  196. /*
  197.  * Try to ensure the composite object free list for sz is not empty.
  198.  * Caller is NOT expected to hold GC_allocate_ml.
  199.  * Returns FALSE if no space is available.
  200.  * Since we are called outside any monitor lock, caller should
  201.  * check the free list after we return.
  202.  */
  203.  
  204. bool GC_allocobj(sz)
  205. long sz;
  206. {
  207.     register struct hblk ** rlp = &(reclaim_list[sz]);
  208.     register bool signalled_full = FALSE; /* Already called GC_heap_full */
  209.     register bool result;
  210.  
  211. #   ifdef VISUALIZE
  212.     window_update();
  213. #   endif
  214.  
  215.     for (;;) {
  216.       /* Attempt to fill free list */
  217.     while (objfreelist[sz] == ((struct obj *)0)
  218.            && *rlp != (struct hblk *)0) {
  219.         /* Safe even if *rlp changed in the interim */
  220.         GC_reclaim_composite(rlp);
  221.     }
  222.  
  223.       if (objfreelist[sz] != (struct obj *)0) {
  224.     return(TRUE);
  225.       }
  226.  
  227.       if (GC_hblkfreelist != 0) {
  228.           XR_MonitorEntry(&GC_allocate_ml);
  229. #      ifdef BLACK_LIST
  230.         if (!is_black_listed(GC_hblkfreelist)
  231.             || GC_sufficient_hb(sz)) {
  232. #      endif
  233.               result = GC_new_hblk(sz);
  234.               XR_MonitorExit(&GC_allocate_ml);
  235.               return(result);
  236. #      ifdef BLACK_LIST
  237.         } else {
  238.               XR_MonitorExit(&GC_allocate_ml);
  239.         }
  240. #      endif
  241.       }
  242.  
  243.       if (signalled_full) break;
  244.       XR_MonitorEntry(&GC_allocate_ml);
  245.       if (GC_DIV * GC_non_gc_bytes < GC_MULT * GC_heapsize
  246.           || GC_fix_heap_size) {
  247.         GC_heap_full();
  248.         signalled_full = TRUE;
  249.       } else {
  250.     GC_expand_hp(NON_GC_HINCR, FALSE);
  251.       }
  252.       XR_MonitorExit(&GC_allocate_ml);
  253.     }
  254.  
  255.     XR_MonitorEntry(&GC_allocate_ml);
  256.     result = GC_new_hblk(sz);
  257.     XR_MonitorExit(&GC_allocate_ml);
  258.     return(result);
  259. }
  260.  
  261. /*
  262.  * The same as above, but for atomic objects.
  263.  */
  264. bool GC_allocaobj(sz)
  265. long sz;
  266. {
  267.     register struct hblk ** rlp = &(areclaim_list[sz]);
  268.     register bool signalled_full = FALSE;
  269.     register bool result;
  270.  
  271. #   ifdef VISUALIZE
  272.     window_update();
  273. #   endif
  274.  
  275.     for (;;) {
  276.       /* Attempt to fill free list */
  277.     while (aobjfreelist[sz] == ((struct obj *)0)
  278.            && *rlp != (struct hblk *)0) {
  279.         /* Safe even if *rlp changed in the interim */
  280.         GC_reclaim_atomic(rlp);
  281.     }
  282.  
  283.       if (aobjfreelist[sz] != (struct obj *)0) {
  284.     return(TRUE);
  285.       }
  286.  
  287.       if (GC_hblkfreelist != 0) {
  288.     XR_MonitorEntry(&GC_allocate_ml);
  289.         result = GC_new_hblk(-sz);
  290.         XR_MonitorExit(&GC_allocate_ml);
  291.     return(result);
  292.       }
  293.  
  294.       if (signalled_full) break;
  295.       XR_MonitorEntry(&GC_allocate_ml);
  296.       if (GC_DIV * GC_non_gc_bytes < GC_MULT * GC_heapsize) {
  297.         GC_heap_full();
  298.         signalled_full = TRUE;
  299.       } else {
  300.     GC_expand_hp(NON_GC_HINCR, FALSE);
  301.       }
  302.       XR_MonitorExit(&GC_allocate_ml);
  303.     }
  304.  
  305.     XR_MonitorEntry(&GC_allocate_ml);
  306.     result = GC_new_hblk(-sz);
  307.     XR_MonitorExit(&GC_allocate_ml);
  308.     return(result);
  309. }
  310.  
  311.